/**
* Definition for singly-linked list.
* 两数相加
* 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
*  */

#include <cmath>
#include <deque>
#include <vector>

struct ListNode {
 int val;
 ListNode *next;
 ListNode() : val(0), next(nullptr) {}
 ListNode(int x) : val(x), next(nullptr) {}
 ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
    {
        ListNode* pl1=l1;
        ListNode* pl2=l2;
        ListNode* EqualLst = new ListNode();
        ListNode* IterEqual=EqualLst;
        int bAddOne = 0;
        while(pl1!=nullptr&&pl2!=nullptr)
        {
            int Value = pl1->val+pl2->val+bAddOne;
            bAddOne = 0;
            int SurPlus = Value%10;
            if(Value>=10)
            {
                bAddOne = 1;
            }
            IterEqual->next = new ListNode(SurPlus);
            IterEqual = IterEqual->next;
            pl1=pl1->next;
            pl2=pl2->next;
        }
        //处理未完成的序列
        if(pl1)
        {
            IterEqual->next = Handle(pl1,bAddOne);
        }
        else if(pl2)
        {
            IterEqual->next = Handle(pl2,bAddOne);
        }
        else if(!pl1&&!pl2&&bAddOne)
        {
            IterEqual->next = new ListNode(bAddOne);
        }
        return EqualLst->next;
    }
    static ListNode* Handle(ListNode* Lst,int bAddOne)
    {
        if(!bAddOne)
        {
            return Lst;
        }
        ListNode* HandleLst = new ListNode();
        ListNode* IterHandle = HandleLst;
        ListNode* Iter = Lst;
        while(Iter)
        {
            int Value = Iter->val + bAddOne;
            bAddOne = 0;
            int Surplus = Value%10;
            IterHandle->next = new ListNode(Surplus);
            if(Value>=10)
            {
                bAddOne = 1;
            }
            IterHandle = IterHandle->next;
            Iter = Iter->next;
        }
        if(bAddOne)
        {
            IterHandle->next = new ListNode(1);
        }
        return HandleLst->next;
    }
    //下面这种解体思路行不通，我还寻思这个难度怎么会是中等，最大有一百位数
    static ListNode* addTwoNumbersDemo(ListNode* l1, ListNode* l2)
    {
        ListNode* lst=new ListNode();
        long int Value = GetNum(l1)+GetNum(l2);
        if(!Value)
        {
            return lst;
        }
        std::deque<int>Stack;
        while(Value!=0)
        {
            int Surplus = Value%10;
            Stack.push_back(Surplus);
            Value /=10;
        }
        ListNode* Iter = lst;
        while (Stack.size())
        {
            ListNode* Node = new ListNode(Stack.front());
            Stack.pop_front();
            Iter->next=Node;
            Iter = Iter->next;
        }
        return lst->next;
    }
    static int GetNum(ListNode* lst)
    {
        if(lst->val==0)
        {
            return 0; 
        }
        long int Value = 0;
        ListNode* Iter = lst;
        Iter = lst;
        for(int i=0;Iter!=nullptr;++i)
        {
            Value+=Iter->val*pow(10,i);
            Iter=Iter->next;
        }
        return Value;
    }
};